package com.zhangxiaofanfan.hotcode.fourth.third;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-100-liked">207. 课程表</a>
 *
 * @author zhangxiaofanfan
 * @date 2024-06-26 20:33:33
 */
public class HotCode053 {
    public static void main(String[] args) {
        HotCode053 hotCode = new HotCode053();
        int[][] prerequisites = {{1, 0}};
        System.out.println(hotCode.canFinish(2, prerequisites));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 保存入度为 0 的节点
        Deque<Integer> deque = new ArrayDeque<>();
        // 到达课程[key]的所有开始节点
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] inorder = new int[numCourses];
        for (int[] course : prerequisites) {
            if (!map.containsKey(course[1])) {
                map.put(course[1], new ArrayList<>());
            }
            map.get(course[1]).add(course[0]);
            inorder[course[0]]++;
        }
        // 将所有入度为 0 的节点保存在队列中
        for (int i = 0; i < numCourses; i++) {
            if (inorder[i] == 0) {
                deque.addLast(i);
            }
        }
        int hasFinishCount = 0;
        while (!deque.isEmpty()) {
            hasFinishCount++;
            Integer first = deque.removeFirst();
            for (Integer course : map.getOrDefault(first, new ArrayList<>())) {
                inorder[course]--;
                if (inorder[course] == 0) {
                    deque.addLast(course);
                }
            }

        }
        return hasFinishCount == numCourses;
    }
}
